//
// Created by francklinson on 2021/11/28 AT 15:50.
// May Saint Diana bless you!
//

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    int MOD = 1'000'000'000 + 7;
    vector<int> primes{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

    int numPrimeArrangements(int n) {
        // 找到1到n之间的质数个数m
        // 质数可以形成m的全排列  剩下的可以形成n-m的全排列
        int primeCounter = int(upper_bound(primes.begin(), primes.end(), n) - primes.begin());
        long long ans = 1;
        for (int i = 1; i <= primeCounter; ++i) {
            ans = (ans * i) % MOD;
        }
        for (int i = 1; i <= (n - primeCounter); ++i) {
            ans = (ans * i) % MOD;
        }
        return ans;


    }

    // 判断是不是质数
    bool isPrime(int x) {
        if (x == 1)
            return false;
        for (int i = 2; i <= sqrt(x); ++i) {
            if (x % i == 0)
                return false;
        }
        return true;
    }

    // 递归求阶乘
    int factorial(int x) {
        if (x == 1)
            return x;
        return x * factorial(x - 1) % MOD;
    }
};

int main() {
    Solution solution;
    cout << solution.numPrimeArrangements(5) << endl;
    cout << solution.numPrimeArrangements(8) << endl;
    cout << solution.numPrimeArrangements(100) << endl;
    return 0;
}

